﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //排序，方便用前面两个较小数之和与后面较大数比较
        sort(nums.begin(), nums.end());
        size_t i = nums.size() - 1, left = 0, right = i - 1, ret = 0;
        while (i >= 2)
        {
            while (left < right)
            {
                    if (nums[left] + nums[right] > nums[i])
                    {
                        ret += right - left;
                        --right;
                    }
                    else
                    {
                        ++left;
                    }
            }

            --i;
            left = 0;
            right = i - 1;
        }
        return ret;
    }
    
    /*
    int triangleNumber(vector<int>& nums) {
        //排序，方便用前面两个较小数之和与后面较大数比较
        sort(nums.begin(), nums.end());
        size_t i = nums.size() - 1, left = 0, right = i - 1, ret = 0;
        while (i >= 2)
        {
            while (left < right)
            {
                while (left < right)
                {

                    if (nums[left] + nums[right] > nums[i])
                    {
                        ret += right - left;
                        break;
                    }
                    else
                    {
                        ++left;
                    }
                }
                //因为arr[left] + arr[right-1] <= arr[left] + arr[right]，故不用重新初始化left = 0 ，left保持当前位置等待下一次移动 

                --right;
            }

            --i;
            left = 0;
            right = i - 1;
        }
        return ret;
    }

    */
};

int main()
{
    Solution s;
    vector<int> v({ 4,2,3,4 });
    cout << s.triangleNumber(v);
	return 0;
}
/*
给定⼀个包含⾮负整数的数组 nums ，返回其中可以组成三⻆形三条边的三元组个数。
⽰例1:
输⼊:nums = [2,2,3,4] 
输出:3 
解释:有效的组合是:
2,3,4 (使⽤第⼀个2)
2,3,4 (使⽤第⼆个2)
2,2,3

*/